#include "AVL.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define Get_H(root) (root == NULL ? 0 : root->h)
#define MAX(a,b) ((a) > (b) ? (a) : (b))

//单向左旋
struct BitNode*SingleRotateWithLeft(struct BitNode*k)
{
    struct BitNode*k1 = k->rchild;
    k->rchild = k1->lchild;
    k1->lchild = k;
    k->h = MAX(Get_H(k->lchild),Get_H(k->rchild)) +1;
    k1->h = MAX(Get_H(k1->lchild),Get_H(k1->rchild)) +1;

    return k1;
}
//单向右旋
struct BitNode*SingleRotateWithRight(struct BitNode*k)
{
    struct BitNode*k1 = k->lchild;
    k->lchild = k1->rchild;
    k1->rchild = k;
    k->h = MAX(Get_H(k->lchild),Get_H(k->rchild)) +1;
    k1->h = MAX(Get_H(k1->lchild),Get_H(k1->rchild)) +1;

    return k1;
   
}
//先左后右
struct BitNode*DoubleRotateLeftRight(struct BitNode*k)
{
   k->lchild = SingleRotateWithLeft(k->lchild);
   return SingleRotateWithRight(k);
   
}
//先右后左
struct BitNode*DoubleRotateRightLeft(struct BitNode*k)
{
   k->rchild = SingleRotateWithRight(k->rchild);
   return SingleRotateWithLeft(k);
   
}
// int Get_H(struct BitNode*root)
// {
//     if(root == NULL)
//         return 0;
//     return root->h
// }
/*
    Insert_Node:往一棵二叉排序树上增加节点，增加之后继续保持其排序性及平衡性
*/
struct BitNode*Insert_Node(struct BitNode*root,TElemType d)
{ 
    if(root == NULL)
    {
        //创建一个新节点并赋值
        struct BitNode*pnew = malloc(sizeof(*pnew));
        if(pnew == NULL)
            return root;
        pnew->data = d;
        pnew->h = 1;
        pnew->lchild = pnew->rchild = NULL;
        return pnew;
    }
    if(d > root->data)// 增加的节点比根节点要大
    {
        root->rchild = Insert_Node(root->rchild,d);
        //更新root的高度
        root->h = MAX(Get_H(root->lchild),Get_H(root->rchild)) + 1;

        //看平衡因子
        if(abs(Get_H(root->lchild) - Get_H(root->rchild)) > 1)//不平衡
        {
            //根据不平衡情况作相应的旋转：在不平衡节点的右子树
            //
            if(d > root->rchild->data)//在不平衡节点的右子树的右边
            {
                //单向左旋
                root = SingleRotateWithLeft(root);
            }
            else
            {
                // 在不平衡节点的右子树的左边： 先右后左
                root = DoubleRotateRightLeft(root);
            }
        }

    }
    else if(d < root->data)// 增加的节点比根节点要小
    {
        root->lchild = Insert_Node(root->lchild,d);
        //更新root的高度
        root->h = MAX(Get_H(root->lchild),Get_H(root->rchild)) + 1;

        //看平衡因子
        if(abs(Get_H(root->lchild) - Get_H(root->rchild)) > 1)//不平衡
        {
            //根据不平衡情况作相应的旋转：在不平衡节点的右子树
            //
            if(d < root->lchild->data)//在不平衡节点的左子树的左边
            {
                //单向右旋
                root = SingleRotateWithRight(root);
            }
            else
            {
                // 在不平衡节点的左子树的右边： 先左后右
                root = DoubleRotateLeftRight(root);
            }
        }
    }
    else
        return root;
    return root;
}
/*
    Create_input_AVLTree:从键盘上输入数据创建一棵平衡的二叉排序树

    参数：无

    返回值：
        返回根节点指针
*/
struct BitNode*Create_input_AVLTree()
{
    struct BitNode*root = NULL;//空树
    while(1)
    {
        TElemType ch;
        scanf("%d", &ch);
        if(ch == 0)
            break;
        
        root = Insert_Node(root, ch);
    }

    return root;
}

//先序遍历
void Pre_order(struct BitNode*root)
{
    if(root == NULL)
        return;
    //先根
    printf("%d ", root->data);
    //左子树
    Pre_order(root->lchild);

    //右子树
    Pre_order(root->rchild);

}
//中序遍历
void Mid_order(struct BitNode*root)
{
    if(root == NULL)
        return;
    
    //左子树
    Mid_order(root->lchild);

    //中根
    printf("%d ", root->data);

    //右子树
    Mid_order(root->rchild);

}
//后序遍历
void Post_order(struct BitNode*root)
{
    if(root == NULL)
        return;
    
    //左子树
    Post_order(root->lchild);

    //右子树
    Post_order(root->rchild);

    //后根
    printf("%d ", root->data);

    

}


